package com.lxw.question;


import java.util.HashMap;

public class Q10 {
    /**
     * 题目描述
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     */
    private static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

    HashMap<Integer,Integer> map = new HashMap<>();//标记中序遍历
    int[] preorder;//保留的先序遍历
    public  TreeNode buildTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
        for(int i = 0 ; i < preorder.length ; i++){
            map.put(inorder[i],i);
        }

        TreeNode node = recursive(0,0,inorder.length-1);
        //遍历操作，前序遍历
        preOrder(node);
        return node;
    }

    public  TreeNode recursive(int pre_root_idx,int in_left_idx,int in_right_idx){
        //相等就是自己
        if(in_left_idx > in_right_idx){
            return null;
        }
        //root_idx是在先序里面的
        TreeNode root = new TreeNode(preorder[pre_root_idx]);
        //有了先序的，再根据先序的，在中序中获取当前根的索引
        int idx = map.get(preorder[pre_root_idx]);
        //左子树的根节点就是左子树的（前序遍历）第一个，就是+1,左边边界就是left，右边边界是中间区分idx-1
        root.left = recursive(pre_root_idx + 1,in_left_idx,idx - 1);
        //由根节点在中序遍历的idx区分2段，idx就是根

        //右子树的根，就是右子树（前序遍历）的第一个，就是当前根节点 加上左子树的数量
        // pre_root_idx 当前的根  左子树的长度 = 左子树的左边-右边 (idx-1 - in_left_idx +1) 。最后+1就是右子树的根了
        root.right = recursive(pre_root_idx + (idx-1 - in_left_idx +1) +1,idx + 1,in_right_idx);
        return root;
    }

    public static void preOrder(TreeNode node){
        //先遍历根节点，再遍历左右孩子节点
        preOrderRe(node);
    }

    private static void preOrderRe(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.val+" ");
        preOrderRe(node.left);
        preOrderRe(node.right);
    }


}
